package com.gxc.graph;

public class Trie {

    private Trie[] tries;
    private boolean end;

    public Trie() {
        tries = new Trie[26];
    }

    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            int n = c - 'a';
            Trie trie = node.tries[n];
            if (trie == null) {
                trie = new Trie();
            }
            node.tries[n] = trie;
            node = trie;
        }
        node.end = true;
    }

    public boolean search(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            node = node.tries[c - 'a'];
            if (node == null) return false;
        }
        return node.end;
    }

    public boolean startsWith(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            node = node.tries[c - 'a'];
            if (node == null) return false;
        }
        return true;
    }
}
